package Leetcode.Stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: kirito
 * @Date: 2024/4/15 12:51
 * @Description:
 * 表现良好的最长时间段
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
 *
 * 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
 *
 * 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
 *
 * 请你返回「表现良好时间段」的最大长度。
 *
 *
 *
 * 示例 1：
 *
 * 输入：hours = [9,9,6,0,6,6,9]
 * 输出：3
 * 解释：最长的表现良好时间段是 [9,9,6]。
 * 示例 2：
 *
 * 输入：hours = [6,6,6]
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= hours.length <= 104
 * 0 <= hours[i] <= 16
 */

public class longestWPI {
    public static void main(String[] args) {
        int[] arr = {9, 9, 6, 0, 6, 6, 9};
        System.out.println(longestWPI(arr));

    }
    /**
     * 狠狠压榨！！！！！！！！！！！麻了麻了
     * 1.9 9  6    9   1这样应该也是可以的
     * 用滑动窗口思路逻辑会很复杂，需要考虑什么时候前进，什么时候后近，但是这个条件又是不确定的
     *
     * 贪心
     *
     * @param hours
     * @return
     */
    // 定义一个函数，计算最长的工作天数序列
    //9 9   6   0   6   6   9
    public static int longestWPI(int[] hours) {
        int n = hours.length; // 获取工时数组的长度
        int[] s = new int[n + 1]; // 创建一个辅助数组，用于存储累积和
        Deque<Integer> stack = new ArrayDeque<Integer>(); // 创建一个栈，用于存储索引
        stack.push(0); // 初始化栈，将0索引压入栈中
        for (int i = 1; i <= n; i++) { // 遍历工时数组
            s[i] = s[i - 1] + (hours[i - 1] > 8 ? 1 : -1); // 更新辅助数组的值
            // 如果当前累积和比栈顶的累积和要大，说明找到了一个新的上升子序列
            if (s[stack.peek()] > s[i]) {
                stack.push(i); // 将当前索引压入栈中
            }
        }

        int res = 0; // 初始化结果变量
        for (int r = n; r >= 1; r--) { // 从数组的末尾开始遍历
            // 当栈不为空，并且栈顶的累积和小于当前的累积和时
            while (!stack.isEmpty() && s[stack.peek()] < s[r]) {
                // 计算当前上升子序列的长度，并更新最大长度
                //  s[stack.peek()] < s[r]   所以stack.peek()到r就一定是一个上升序列，求差值就是题目要的答案
                res = Math.max(res, r - stack.pop());
            }
        }
        return res; // 返回最长上升子序列的长度
    }

    /**
     * 用一个map存储之前能存的满足要求的的索引
     * 前缀和的思想
     *
     * 1.当遍历到下标;时，如果 sum>0，则以下标;结尾的最长子数组的长度为i+1，该子数组为表现良好的时间段。不存在以下标;结尾且长度大于i+1的子数组。
     * 2.假设 ェ 和 y都是数组的前缀和，且 y<r<0。由于计算前缀和时每次将前缀和加 1 或减 1，
     * 因此在前缀和首次变成y之前，前缀和一定会经过 -1 到 y+1 的每个整数。由于 y+1≤:≤-1，
     * 因此在前缀和首次变成 y之前，前缀和一定会经过 ，即前缀和 :的第一次出现的下标一定小于前缀和 y的第一次出现的下标。
     * 当遍历到下标;时，如果 sum<0 且存在以i结尾的表现良好的时间段，只需要考虑前缀和 sum-1的第一次出现的下标j，
     * 则以讠结尾的表现良好的最长时间段的长度一定是i-j，任何小于 sum-1的前缀和如果存在则第一次出现的下标一定大于 j。
     * @param hours
     * @return
     */
    public static int longestWPI2(int[] hours) {
        int n = hours.length; // 获取工时数组的长度
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 创建一个哈希映射，用于存储累积和及其首次出现的索引
        int s = 0, res = 0; // 初始化累积和和结果变量
        for (int i = 0; i < n; i++) { // 遍历工时数组
            s += hours[i] > 8 ? 1 : -1; // 更新累积和
            if (s > 0) { // 如果累积和大于0，说明当前处于上升状态
                res = Math.max(res, i + 1); // 更新结果
            } else { // 如果累积和小于等于0，需要查找之前的上升状态的结束位置
                /*
                1.为什么是s-1,不能是s  s+1？
                    如果s[i]>0 则存在i+1项元素是满足要求的
                    如果s[i]<0 ......
                2.为什么是i - map.get(s - 1)


                感觉可以这么思考  当前s-1已经是不符合条件的了  但是s可能是当前i的位置符合条件，但是前面负的太多了
                导致仍然进入了else判断，所以可以分两种情况
                1.当前i也不符合，且s-1存在：易得res = Math.max(res, i - map.get(s - 1));的res会更小，所以不会覆盖
                2.当前i符合，这样的话s-1肯定是存在的。
                    假设不想要那些s-1的前缀和的数了，求max的两数距离之差
                    因为s-1已经是负的了，所以尽可能不要她，就去就两数距离只差
                    s-(s-1)=1
                感觉也不是。。。好难理解
                 */
                if (map.containsKey(s - 1)) { // 如果哈希映射中存在累积和减1的键
                    res = Math.max(res, i - map.get(s - 1)); // 计算上升子序列的长度，并更新结果
                }
            }
            // 如果当前累积和不在哈希映射中，则将其与索引放入映射中
            if (!map.containsKey(s)) {
                map.put(s, i);
            }
        }
        return res; // 返回最长上升子序列的长度
    }


}
